package com.likeycy.my.sort.cmp;

/**
 * @ClassName: HeapSort
 * @Description: 堆排序：重点！！！
 * @Author: sodagreen
 * @Date: 2021/3/27 6:28
 * @Version: 1.0
 */
public class HeapSort<T extends Comparable<T>> extends Sort<T> {

    private int heapSize;

    @Override
    protected void sort() {

        heapSize = array.length;
        // 原地建堆
        // 自下而上的下滤，采取这种方法批量建堆性能最好
        for (int i = (heapSize >> 1) -1; i >= 0; i--) {
            siftDown(i);
        }

        while (heapSize > 1) {
            // 交换对顶元素与尾部元素
            /*swap(0, heapSize -1);
            heapSize--;*/
            swap(0, --heapSize);

            //对0位置进行下滤（恢复堆的性质，大顶堆则将最大的恢复到堆顶根节点，小顶堆将最小的恢复到堆顶根节点）
            siftDown(0);
        }
    }

    /**
     * 下滤
     * @param index
     */
    private void siftDown(int index) {
        T curTopValue = array[index];
        // 等同于 size除以2。右移一位表示除以2，右移两位表示除以2的平方，以此类推
        // 这里是计算非叶子节点数量。二叉堆的叶子节点的索引 == 非叶子节点的数量。公式为 floor(n/2)
        int half = heapSize >> 1;
        // 找到第一个叶子节点后，那么往后的每个索引都是叶子节点。
        // 必须保证 index 位置是非叶子节点。这是因为非叶子节点才有左右子节点，而叶子节点是没有子节点的
        while (index < half) {
            // index有两种情况：
            // 1.只有单一一个左子节点
            // 2.有完整的左右子节点

            // 默认为左子节点跟它进行比较。左移一位等同于乘以2，左移两位等同于乘以2的平方，以此类推
            int leftChildIndex = (index << 1) + 1;
            T leftChildValue = array[leftChildIndex];
            // 右子节点 (index << 1) + 2 == (index << 1) + 1 + 1
            int rightChildIndex = leftChildIndex + 1;

            // 选出左右子节点最大的那个
            if (rightChildIndex < heapSize
                    && comparatorToElements(array[rightChildIndex], leftChildValue) > 0) {
                leftChildIndex = rightChildIndex;
                leftChildValue = array[rightChildIndex];
            }

            // 这里处理第一种情况
            if (comparatorToElements(curTopValue, leftChildValue) >= 0) {
                break;
            }

            // 执行到此处表示子节点大于根节点的值
            // 将子节点的值放到 index 位置
            array[index] = leftChildValue;
            // 重新设置 index
            index = leftChildIndex;
        }
        array[index] = curTopValue;

    }
}
